package cn.micai.base.string;

import java.util.LinkedHashMap;
import java.util.Map;

/**
 * 描述：在字符串中找到第一个非重复字符
 * <p>
 *
*    其中一个面试问题是“你如何在字符串中找到第一个不重复的字符。”
     例如:
     如果输入字符串是“类比”，那么程序应该返回“n”
     如果输入字符串是“最简单的”，那么程序应该返回'a'

     第一种方法:
     我们将使用LinkedHashMap在字符串中找到第一个非重复字符。

     算法:
     在遍历字符串时获取字符
     把这个字符放在LinkedHashMap中。如果角色已经在那里，增加计数1。
     在迭代时从LinkedHashMap中获得计数。如果计数为1，则返回该字符作为LinkedHashMap保持插入顺序。

     第二种方法
     算法:
     遍历字符串的每个字符。
     如果lastIndexOf和indexOf返回相同的值，那么它就是字符串中的第一个非重复字符。
 *
 * @author: 赵新国
 * @date: 2018/6/11 11:51
 */
public class GetFirstNonRepeatingCharacterMain {

    public static void main(String [] args) {
        System.out.println("First non repeated character for String analogy is : " + getNonRepeatedCharacter("analogy"));
        System.out.println("First non repeated character for String easiest is : " + getNonRepeatedCharacter("easiest"));
    }

    /**
     * 第一种方法
     * @param str
     * @return
     */
    /*public static Character getNonRepeatedCharacter(String str) {
        Map<Character, Integer> countCharacters = new LinkedHashMap<>();
        for (int i=0; i < str.length(); i++) {
            Character c = str.charAt(i);
            if (!countCharacters.containsKey(c)) {
                countCharacters.put(c, 1);
            } else {
                countCharacters.put(c, countCharacters.get(c) + 1);
            }
        }
        // As LinkedHashMap maintains insertion order, first character with
        // count 1 should return first non repeated character
        for (Map.Entry<Character, Integer> e : countCharacters.entrySet()) {
            if (e.getValue() == 1) {
                return e.getKey();
            }
        }
        return null;
    }*/

    /**
     * 第二种方法
     * @param str
     * @return
     */
    public static Character getNonRepeatedCharacter(String str) {
        char[] chars = str.toCharArray();
        for (int i=0; i<str.length(); i++) {
            if (str.lastIndexOf(chars[i]) == str.indexOf(chars[i])) {
                return chars[i];
            }
        }
        return null;
    }
}
